package 矩阵;

/**
 * 289. 生命游戏
 *
 * 根据 百度百科 ， 生命游戏 ，简称为 生命 ，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。
 *
 * 给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态： 1 即为 活细胞 （live），或 0 即为 死细胞 （dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：
 *
 * 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
 * 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
 * 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
 * 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
 * 下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是 同时 发生的。给你 m x n 网格面板 board 的当前状态，返回下一个状态。
 * 给定当前 board 的状态，更新 board 到下一个状态。
 * 注意 你不需要返回任何东西。
 *
  思路：注意题意，每个细胞的状态改变都是实时发生的，所以我们需要遍历，第一次遍历的时候，需要标记哪些位置上的细胞需要改变状态，然后第二次遍历的时候，才改变细胞状态。

  解题步骤：
    1：状态标识:
        使用两位数字表示细胞的状态变化： 使用两位数字，低位表示当前状态，高位表示下一状态
        低位表示当前状态：
            0表示死细胞：
            1表示活细胞；
        高位表示下一状态：
            0表示下一状态是死细胞；
            1表示下一状态是活细胞；
    2：计算每个细胞周围的活细胞数量。（上下左右8个区域）
        定义方向数组 dx 和 dy 来遍历八个邻居。
        1对每个细胞，统计其周围八个方向的活细胞数量。
    3：应用生命游戏的规则：
        第一次遍历数组，根据活细胞数量和当前状态，决定下一状态，并用上述编码记录。
    4：更新网格状态：
        第二次遍历数组，根据统计的编码更新细胞状态（统一右移一位）

 */
public class L_289 {
    public void gameOfLife(int[][] board) {
        if(board == null || board.length == 0 || board[0].length == 0){
            return;
        }
        int row = board.length;
        int col = board[0].length;


        // 2: 定义方向数组，表示上下左右8个方向
        int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1}; // 以x轴为维度的8个方向
        int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1}; // 以y轴为维度的8个方向

        // 3：第一次遍历，标记状态
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                // 获取当前细胞周围8个邻居的活细胞数量
                int live = 0;
                // 统计8个邻居的活细胞数量
                for (int k = 0; k < 8; k++){
                    // 根据方向数组获取邻居坐标
                    int ni = i+dx[k];
                    int nj = j+dy[k];
                    if(ni >= 0 && ni < row && nj >= 0 && nj < col){
                        // 取当前位状态（低位）
                        live += board[ni][nj] & 1;
                    }
                }
                // 根据周围邻居的活细胞状态对当前细胞进行状态标记（决定当前细胞的下一个状态）
                if((board[i][j] &1) == 1){ // 当前是活细胞
                    if(live < 2 || live > 3){
                        board[i][j] = 1; // 活1 -> 死0，下一状态为0 （01）
                    }else {
                        board[i][j] = 3; // 活 -> 活， 下一状态为1 （11）
                    }
                }else { // 当前是死细胞
                    if(live == 3){
                        board[i][j] = 2; // 死 -> 活， 下一状态为1 （10）
                    }else {
                        board[i][j] = 0; // 死 -> 死，下一状态为0 （00）
                    }
                }
            }
        }

        // 4: 第二次遍历，更新状态 （统一右移一位，用高位设置细胞状态）
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                board[i][j] >>= 1;
            }
        }
    }

}
